'''
Created on Jul 15, 2011

@author: vakumar
'''

class Tower(list):
    def __init__(self, n = 0, ls = []):
        #super(Tower, self).__init__(ls)
        if len(ls) == 0: ls = range(1,n+1)
        ls.sort()
        ls.reverse()
        super(Tower, self).__init__(ls)
        #self.ls = ls


    def isappendable(self, item):
        if len(self) == 0: return True
        t = self[len(self) - 1]
        return True if t > item else False
    
    def append(self, item):
        if self.isappendable(item):
            super(Tower,self).append(item)
        else: return -1
    
#    def pop(self):
#        return self.ls.pop() 
#    
#    def __len__(self):
#        return super(Tower,self).__len__()
    
#    def __repr__(self):
#        return super(Tower,self).__repr__()
    

class play_toh(object):
    def __init__(self, n = 5):
        self.n = n
        self.src = Tower(n)
        self.tgt = Tower()
        self.temp = Tower()
        self.ctr = 0
        self.dp = True
        self.d = self._getdict()
        
    def solve_toh(self):
        self.display_towers()
        self.dp = True
        self._solve_it(self.n, self.src, self.tgt, self.temp)
        
    def _solve_it(self,n,s,e,tmp):
        if n == 1 : 
            return self.makemove(s,e)
        else:
            a = self._solve_it(n-1,s,tmp,e)
            b = self._solve_it(1, s, e, tmp)
            c = self._solve_it(n-1,tmp,e,s)
            if not a == b == c == None:
                return -1

    def set(self, n , ls = []):
        self.src = Tower(n)
        self.n = n
        self.tgt = Tower()
        self.temp = Tower()
        self.ctr = 0
        self.d = self._getdict()
        self.display_towers()

    def reset(self):
        self.src = Tower(self.n)
        self.tgt = Tower()
        self.temp = Tower()
        self.ctr = 0
        self.d = self._getdict()
        self.display_towers()

    
    def new(self, n = 0):
        if n == 0:
            t = raw_input("Number of Discs? : ")
            n = int(t)
        self.set(n)
        
    def play(self):        
        num = raw_input("Number of Discs?(default is 5) : ")
        if num and num != '':
            self.set(int(num))
        print '*'*70
        print '''Three Tower 1, 2, 3. U've to give i/p in form of
                 s t (eg. 1 3)
                 where s : source Tower Number for that Move
                       t : Target Tower Number for that Move
                 U can end the game by typing 
                 'quit'
                 Other commands are:
                 reset : to reset the game
                 new: to renew game'''
        print '*'*70
        self.display_towers()
        print """Your job is to move the Discs of T1 to T2
                 All the best!!!"""
        print '*'*70
        d =  self._getdict()
        t = raw_input('move :>')
        #mv_flag = True
        while not t == 'quit':
            #t = raw_input('move :> ')
            if t == 'new':
                n = raw_input("number of discs ? : ")
                self.set(int(n))
                d = self._getdict()
                #continue
            elif t == 'reset' :
                self.reset()
                d = self._getdict()
                print "u restarted the game..."
                #continue
            elif ' ' in t:
                s, e = t.split()
                self.makemove(d[s], d[e])
#                if x != None and x == -1:
#                    mv_flag = self.check_possibilities()
            win = self.win()
            if win:
                print 'U Won!!!'
                print 'U took %s Moves, Problem can be solved in %s moves...' %(self.ctr, int(2**self.n - 1))
                t = raw_input("new/reset/quit??? : ")
                continue
            t = raw_input('move :>')

#            mv_flag = self.check_possibilities()
#
#            if not mv_flag:
#                print "No more Valid Move Left..."
#                print "U loose..."
#                t = raw_input("new/reset/quit??? : ")   
    
    def win(self):
        ls = range(1,self.n + 1)
        ls.reverse()
        return self.tgt == ls
                
    def _getdict(self):
        return {'1': self.src,
                '2': self.tgt,
                '3': self.temp} 
           
#    def check_possibilities(self):
#        a = b = c = True
#        if self.src:
##            print len(self.src)
##            print self.src
#            item = self.src[len(self.src)-1]
#            a = self.tgt.isappendable(item) or self.temp.isappendable(item)
#        if self.tgt:
#            item = self.tgt[len(self.tgt) - 1]
#            b = self.src.isappendable(item) or self.temp.isappendable(item)
#        if self.temp:
#            item = self.temp[len(self.tgt) - 1]
#            c = self.tgt.isappendable(item) or self.src.isappendable(item)
#        return a or b or c
           
    
    def makemove(self, s,t):
        self.ctr += 1
        i = None
        if len(s) > 0 : i = s.pop()
        else:
            print 'src empty...' 
            return -1            
        if t.append(i) == -1:
            s.append(i)
            print 'move not possible...'
            return -1
        if self.dp:
            print 'move # %d' %self.ctr
            self.display_towers()
    
    def display_towers(self):
        print 'T1: %s' %self.src
        print 'T2: %s' %self.tgt
        print 'T3: %s' %self.temp
    
    
    

if __name__ == '__main__':
    game = play_toh(5)
    game.play()